package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TreeProblem;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * 骚气方法多的是.
 * 1. 使用前序中序还原树的思路.
 * 2. 使用LeetCode本身的序列化为数组的思路.
 * 3. JSON encode和decode, 不过要引入外部库.
 * 4. 层次遍历, 加入很多null.
 * 5. 括号嵌套
 * 6. 网络协议或者HFile这种的序列化, 就是固定长度格式的, 或者把长度写进数据里的.
 * <p>
 * <p>
 * 错误写法, 对于有重复值怎么办?
 *
 * @author tzp
 * @since 2020/10/13
 */
public class LC297_1 implements TreeProblem {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "";
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.add(root);
        StringBuilder sb = new StringBuilder();
        while (stack.size() > 0) {
            TreeNode node = stack.pollLast();
            sb.append(nodeToString(node)).append(";");
            if (node.right != null) stack.offerLast(node.right);
            if (node.left != null) stack.offerLast(node.left);
        }
        if (sb.charAt(sb.length() - 1) == ';') {
            sb.deleteCharAt(sb.length() - 1);
        }
        return sb.toString();
    }

    public String nodeToString(TreeNode node) {
        String result = String.valueOf(node.val);
        result += node.left == null ? ",null" : "," + node.left.val;
        result += node.right == null ? ",null" : "," + node.right.val;
        return result;
    }

    Map<Integer, TreeNode> map = null;
    TreeNode root = null;

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) return null;
        map = new HashMap<>();
        root = null;
        for (String node : data.split(";")) {
            stringToNode(node);
        }
        return root;
    }

    public void stringToNode(String data) {
        String[] split = data.split(",");
        int a = Integer.parseInt(split[0]);
        map.computeIfAbsent(a, TreeNode::new);
        if (root == null) root = map.get(a);
        if (!"null".equals(split[1])) {
            int b = Integer.parseInt(split[1]);
            map.computeIfAbsent(b, TreeNode::new);
            map.get(a).left = map.get(b);
        }
        if (!"null".equals(split[2])) {
            int c = Integer.parseInt(split[2]);
            map.computeIfAbsent(c, TreeNode::new);
            map.get(a).right = map.get(c);
        }
    }

    public static void main(String[] args) {
//        Integer[] a = {1, 2, 4, 3, 5, 7, 10, 6, null, 8, null, 11, 9, 15, null, null, null, 12, null, null, null, 13, null, null, null, null, 14};
        Integer[] a = {4, -7, -3, null, null, -9, -3, 9, -7, -4, null, 6, null, -6, -6, null, null, 0, 6, 5, null, 9, null, null, -1, -4, null, null, null, -2};
        TreeNode treeNode = TreeNode.arrayToTreeNode(a);
        String xx = new LC297_1().serialize(treeNode);
        System.out.println(xx);
        TreeNode oo = new LC297_1().deserialize(xx);
        System.out.println(oo);
    }
}
